Hot game

In combinatorial game theory, a branch of mathematics, a hot game is one in which each player can improve their position by making the next move.

For example, consider a game in which players alternately remove tokens of their own color from a table, the Blue player removing only blue tokens and the Red player removing only red tokens, with the winner being the last player to remove a token. Obviously, victory will go to the player who starts off with more tokens, or to the second player if the number of red and blue tokens are equal. Removing a token of one's own color leaves the position slightly worse for the player who made the move, since that player now has fewer tokens on the table. Thus each token represents a "cold" component of the game.

Now consider a special purple token bearing the number "100", which may be removed by either player, who then replaces the purple token with 100 tokens of their own color. (In the notation of Conway, the purple token is the game {100|−100}.) The purple token is a "hot" component, because it is highly advantageous to be the player who removes the purple token. Indeed, if there are any purple tokens on the table, players will prefer to remove them first, leaving the red or blue tokens for last. In general, a player will always prefer to move in a hot game rather than a cold game, because moving in a hot game improves their position, while moving in a cold game injures their position.

The temperature of a game is a measure of its value to the two players. A purple "100" token has a temperature of 100 because its value to each player is 100 moves. In general, players will prefer to move in the hottest component available. For example, suppose there is a purple "100" token and also a purple "1,000" token which allows the player who takes it to dump 1,000 tokens of their own color on the table. Each player will prefer to remove the "1,000" token, with temperature 1,000 before the "100" token, with temperature 100.

To take a slightly more complicated example, consider the game {10|2} + {5|−5}. {5|−5} is a token which either player may replace with 5 tokens of their own color, and {10|2} is a token which the Blue player may replace with 10 blue tokens or the Red player may replace with 2 blue tokens.

The temperature of the {10|2} component is ½(10 − 2) = 4, while the temperature of the {5|−5} component is 5. This suggests that each player should prefer to play in the {5|−5} component. Indeed, the best first move for the Red player is to replace {5|−5} with −5, whereupon the Blue player replaces {10|2} with 10, leaving a total of 5; had the Red player moved in the cooler {10|2} component instead, the final position would have been 2 + 5 = 7, which is worse for Red. Similarly, the best first move for the Blue player is also in the hotter component, from {5|-5} to 5, even though moving in the {10|2} component produces more blue tokens in the short term.

Snort

In the game of Snort, Red and Blue players take turns coloring the vertices of a graph, with the constraint that two vertices that are connected by an edge may not be colored differently. As usual, the last player to make a legal move is the winner. Since a player's moves improve their position by effectively reserving the adjacent vertices for them alone, positions in Snort are typically hot. In contrast, in the closely related game Col, where adjacent vertices may not have the same color, positions are usually cold.

Applications

The theory of hot games has found some application in the analysis of endgame strategy in Go.[1][2]

See also

References

Notes

  1. ^ Elwyn Berlekamp and David Wolfe (1994), Mathematical Go: Chilling Gets the Last Point.
  2. ^ A bibliography is given in Conway 2001, p. 108